package LC;

/**
 * https://leetcode.com/problems/merge-k-sorted-lists/description/
 * Merge k sorted linked lists and return it as one sorted list.
 * Analyze and describe its complexity.
 */
public class LC_023_MergekSortedLists_LinkedList_BinarySearch {
    public static void main(String[] args) {
        ListNode head1 = new ListNode(0);
        head1.next = new ListNode(1);
        head1.next.next = new ListNode(2);
        head1.next.next.next = new ListNode(3);

        ListNode head2 = new ListNode(1);
        head2.next = new ListNode(2);
        head2.next.next = new ListNode(3);
        head2.next.next.next = new ListNode(4);

        ListNode head3 = new ListNode(0);
        head3.next = new ListNode(2);
        head3.next.next = new ListNode(4);
        head3.next.next.next = new ListNode(6);

        ListNode[] lists = new ListNode[]{head1, head2, head3};
        ListNode mergeKLists = Solution.mergeKLists(lists);
        printList(mergeKLists);
    }

    static class ListNode {
        int val;
        ListNode next;

        public ListNode(int x) {
            this.val = x;
        }
    }

    private static void printList(ListNode head) {
        ListNode cur = head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
    }

    static class Solution {
        static ListNode mergeKLists(ListNode[] lists) {
            int len = lists.length;
            if (len == 0)
                return null;
            if (len == 1)
                return lists[0];
            //二分法查找表，类似于希尔排序算法
            while (len > 1) {
                int mid = (len + 1) >> 1;
                for (int i = 0; i < len >> 1; i++) {
                    lists[i] = mergeTwoLists(lists[i], lists[i + mid]);
                }
                len = mid;
            }

            return lists[0];
        }

        //合并两个链表记录
        private static ListNode mergeTwoLists(ListNode L1, ListNode L2) {
            if (L1 == null) return L2;
            if (L2 == null) return L1;
            ListNode head = new ListNode(0);
            ListNode phead = head;
            while (L1 != null && L2 != null) {
                if (L1.val <= L2.val) {
                    phead.next = L1;
                    phead = phead.next;
                    L1 = L1.next;
                } else {
                    phead.next = L2;
                    phead = phead.next;
                    L2 = L2.next;
                }
            }
            if (L1 != null)
                phead.next = L1;
            else
                phead.next = L2;
            return head.next;
        }
    }

}
